package practice;

import java.util.PriorityQueue;

public class Day28 {
    static class MedianFinder {
        PriorityQueue<Integer> maxTree;
        PriorityQueue<Integer> minTree;
        public MedianFinder() {
            //是大根堆
            maxTree = new PriorityQueue<>((a,b)->{
                return b.compareTo(a);
            });
            //minTree是小根堆，小根堆里面的所有值都比大根堆中大，这样能保证在长度相差只有1的时候，大根堆里面的堆顶元素就是中间值
            //相差为0的时候，中间值就是大小跟堆的堆顶元素的和除2
            minTree = new PriorityQueue<>();
        }

        public void addNum(int num) {
            int max = maxTree.size();
            int min = minTree.size();
            if(max == min) {
                if(max == 0 || num <= maxTree.peek()) {
                    maxTree.offer(num);
                }else {
                    minTree.offer(num);
                    maxTree.offer(minTree.poll());
                }
            }else if(max == min+1) {
                if(num >= maxTree.peek()) {
                    minTree.offer(num);
                }else {
                    maxTree.offer(num);
                    minTree.offer(maxTree.poll());
                }
            }
        }

        public double findMedian() {
            if(maxTree.size() == minTree.size()) {
                return (maxTree.peek() + minTree.peek()) / 2.0;
            }else if(maxTree.size() == minTree.size() + 1) {
                return maxTree.peek();
            }else {
                return 0;
            }
        }
    }
}
